package ext;
import java.io.BufferedReader;
import java.io.FileReader;

import org.junit.*;

public class SensitiveWord {

    private static final TireTree tt = new TireTree();

    static {
        try (
            FileReader fr = new FileReader("src/res/sens.txt");
            BufferedReader br = new BufferedReader(fr);    
        ) {
            String line;
            while ((line = br.readLine()) != null) {
                tt.insert(line);
            }
            System.out.println(tt.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        System.out.println(tt.filter("cdef"));
    }

    public static String filter(String s) {
        return tt.filter(s);
    }
    
    static class TireTree {
        Node root;

        public TireTree() {
            root = new Node();
        }

        public String filter(String s) {
            char[] cs = s.toCharArray();
            StringBuilder sb = new StringBuilder();
            
            loop: for (int i = 0; i < cs.length; i++) {
                if (isFirst(cs[i])) {
                    Node cur = root;
                    int j = i;
                    while (j < cs.length && cur != null) {
                        if (cs[j] == '*') {
                            j++;
                            continue;
                        }
                        Node next = cur.getNext(cs[j++]);
                        if (next == null) {
                            break;        
                        } else if (next.isEnd()) {
                            sb.append("***");
                            i = j - 1;
                            continue loop;
                        }
                        cur = next;
                    }
                    if (j == cs.length) {
                        sb.append(cs[i]);
                    }
                } else {
                    sb.append(cs[i]);
                }
            }
            return sb.toString();
        }

        public boolean isFirst(char c) {
            return root.getNext(c) != null;
        }

        public void insert(String s) {
            char[] cs = s.toCharArray();
            Node cur = root;
            for (char c: cs) {
                Node next = cur.getNext(c);
                if (next == null) {
                    next = cur.setNext(c);
                }
                cur.increseTime();
                cur = next;
            }
            cur.setEnd();
        }

        public boolean match(String s) {
            char[] cs = s.toCharArray();
            Node cur = root;
            for (char c: cs) {
                Node next = cur.getNext(c);
                if (next == null) {
                    return false;
                }
                cur = next;
            }
            return cur.isEnd();
        }

        public int size() {
            return root.getTime();
        }
    }

    static class Node {
        Node[] nexts;
        int time = 0;
        boolean end;

        public Node() {
            nexts = new Node[26];
        }

        public Node getNext(char c) {
            return nexts[c - 'a'];
        }

        public Node setNext(char c) {
            nexts[c - 'a'] = new Node();
            return nexts[c - 'a'];
        }

        public int getTime() {
            return time;
        }

        public void increseTime() {
            this.time++;
        }

        public boolean isEnd() {
            return end;
        }

        public void setEnd() {
            this.end = true;
        }  
    }

    @Test
    public void test() {
        TireTree tt = new TireTree();
        tt.insert("abc");
        System.out.println(tt.match("abc"));;
        tt.insert("ab");
        System.out.println(tt.match("ab"));;

    }
}
